A typical integrated circuit (IC) design flow often includes a logical design and a physical design. A logic design may include the following steps: (1) design entry (to enter the design into an IC design system, either using a hardware description language or schematic entry); (2) logical synthesis (to use a hardware description language such as VHDL or Verilog or the like and a logical synthesis tool to produce a netlist, which is a description of logical cells and their connections); (3) system partitioning (to divide a large system into small pieces); and (4) pre-layout simulation (to check whether a design functions correctly). A physical design may include the following steps: (1) floorplanning (to arrange blocks of a netlist on a chip); (2) placement (to decide the location of cells in a block); (3) routing (to make connections between cells and blocks); (4) extraction (to determine resistance and capacitance of the interconnect); and (5) post-layout simulation (to check whether the design still works with the added loads of the interconnect).
Once the IC designer has floorplanned a chip and logic cells within the flexible blocks have been placed, it is time to make the connections by routing the chip. Routing is usually divided into global routing and detailed routing. In global routing, connections are completed between the proper blocks of the IC, disregarding the exact geometric details of each wire and terminal. For each wire, a global router finds a list of channels that are to be used as a passageway for that wire. In other words, global routing specifies the loose route of a wire through different regions of the routing space. Thus, a global router does not make any connections—it just plans them. Global routing is followed by detailed routing which completes point-to-point connections between terminals on the blocks. Loose routing is converted into exact routing by specifying the geometric information such as width of wires and their layer assignments. Detailed routing includes the exact channel routing of wires.
The input to a global router is a floorplan that includes the location of all fixed and flexible blocks, the placement information for flexible blocks, and the location of all logical cells. The goal of global routing is to provide complete instructions to the detailed router on where to route every net. Global routing tries to achieve at least one of the following objectives: (1) to minimize the total interconnect length; (2) to maximize the probability that detailed router can complete the routing; and (3) to minimize the critical path delay. Many methods used in global routing are based on the solution to the tree on a graph problem. Therefore, it would be desirable to provide a method and apparatus for performing logical transformations for global routing to optimizing design parameters.